package test2.算法.二分查找;

public class App {
	
	public static void main(String[] args) {
//		int[] arr = new int[10];
//		for(int i=0;i<10;i++) {
//			Random r = new Random(i);
//			arr[i] = r.nextInt(100);
//		}
//		Arrays.sort(arr);
//		printArray(arr);
		
		int[] arr = new int[]{8,11,34,36,60,62,64,85,87,89};
		System.out.println(search1(arr, 0, arr.length, 85));
		System.out.println(search2(arr, 85));
	}
	
	public static void printArray(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i] + ",");
		}
		System.out.println();
	}
	
	/**
	 * 递归
	 * @param arr
	 * @param start
	 * @param end
	 * @param obj
	 * @return
	 */
	public static int search1(int[] arr, int start, int end, int obj) {
		int mid = (start + end)/2;
		int val = arr[mid];
		int result = 0;
		if(obj<val) {
			result = search1(arr, start, mid, obj);
		} else if(obj>val) {
			result = search1(arr, mid, end, obj);
		} else {
			result = mid;
		}
		return result;
	}
	
	/**
	 * 循环
	 * @param arr
	 * @param obj
	 * @return
	 */
	public static int search2(int[] arr, int obj) {
		int start = 0;
		int end = arr.length-1;
		int result = 0;
		while(true) {
			int mid = (start + end)/2;
			int val = arr[mid];
			if(obj<val) {
				end = mid;
			} else if(obj>val) {
				start = mid;
			} else {
				result = mid;
				break;
			}
		}
		return result;
	}

}
